#include <fstream>
#include "fast_vector.h"
#include <string>
#include <cmath>
#include <stdexcept>
#include "big_int.h"

big_int::big_int(int num) : is_negative_(num < 0), digits_()
{
   digits_.push_back(std::abs(num));
}

big_int::big_int(const fast_vector &digits, bool is_negative) : digits_() , is_negative_(is_negative)
{
   digits_ = digits;
}

big_int::big_int(const std::string& input)
{
   std::string number = input;
   if (number == "0")
   {
      *this = big_int();
      return;
   }
   is_negative_ = false;
   if (number[0] == '-' || number[0] == '+')
   {
      if (number[0] == '-')
         is_negative_ = true;
      number = number.substr(1, number.size());
   }
   digits_.clear();
   int x = 0;
   int tmp = 1;
   for (int i = number.length() - 1; i >= 0; i--) 
   {
      x += (number[i] - '0') * tmp;
      tmp *= 10;
      if (tmp == BASE)
      {
         digits_.push_back(x);
         tmp = 1;
         x = 0;
      }
   }
   if (x != 0)
      digits_.push_back(x);
   cut_zeroes();
}

big_int::big_int(big_int const &a)
{
   is_negative_ = a.is_negative_;
   digits_ = a.digits_;
}

void big_int::swap(big_int & a)
{
   std::swap(is_negative_, a.is_negative_);
   digits_.swap(a.digits_);
}

big_int& big_int::operator =(const big_int &b)
{
   digits_ = b.digits_;
   is_negative_ = b.is_negative_;
   return *this;
}

big_int& big_int::operator *=(const big_int& b)
{
   size_t len_a = digits_.size();
   size_t len_b = b.digits_.size();
   big_int c = big_int();
   is_negative_ = is_negative_ ^ b.is_negative_;
   c.digits_.resize(len_a + len_b);
   for (size_t i = 0; i < len_a; i++)
   {
      long long t = 0;
      for (size_t j = 0; j < len_b; j++)
      {
         t += c.digits_[i + j] + static_cast<long long>(digits_[i]) * b.digits_[j];
         c.digits_[i + j] = static_cast<int>(t % BASE);
         t /= BASE;
      }
      size_t j = len_b + i;
      while (t != 0)
      {
         c.digits_[j] = static_cast<int>(t % BASE);
         t = t / BASE;
         j++;
      }
   }
   c.cut_zeroes();
   digits_ = c.digits_;
   if (is_zero())
      is_negative_ = false;
   return *this;
}

big_int& big_int::operator -=(const big_int& q)
{
   if (is_negative_ && q.is_negative_)
   {
      *this =  q.abs() -= abs();
      return *this;
   }
   if (!is_negative_ && q.is_negative_)
   {
      *this = abs() += q.abs();
      return *this;
   }
   if (is_negative_ && !q.is_negative_)
   {
     *this = -(abs() += q.abs());
     return *this;
   }
   if (*this < q)
   {
      *this = -(q.abs() -= abs());
      return *this;
   }
   big_int b = q;

   size_t len_a = digits_.size();
   size_t len_b = b.digits_.size();

   for (size_t i = 0; i < len_a; i++)
   {
      int x;
      if (i < len_b)
         x = b.digits_[i];
      else 
         x = 0;
      this->digits_[i] -= x;
      if (this->digits_[i] < 0)
      {
         this->digits_[i] += BASE;
         this->digits_[i + 1] -= 1;
      }
   }
   this->cut_zeroes();
   return *this;
}

big_int& big_int::operator /=(const big_int& divider)
{
   *this = divide_with_remainder(divider).first;
   return *this; 
}

big_int& big_int::operator %=(const big_int& divider)
{
   *this = divide_with_remainder(divider).second;
   return *this; 
}

big_int& big_int::operator +=(const big_int& b)
{
   if (is_negative_ && b.is_negative_)
   {
      *this = -(abs() += b.abs());
      return *this;
   }
   if (!is_negative_ && b.is_negative_)
   {
      *this = abs() -= b.abs();
      return *this;
   }
   if (is_negative_ && !b.is_negative_)
   {
      *this = b.abs() -= abs();
      return *this;
   }
   size_t len_a = digits_.size();
   size_t len_b = b.digits_.size();
   long long remainer = 0;
   for (size_t i = 0, len = std::max(len_a, len_b); i < len; i++)
   {
      int x, y;
      if (i >= len_a)
         x = 0;
      else
         x = digits_[i];
      if (i >= len_b)
         y = 0;
      else
         y = b.digits_[i];
      remainer = x + y + remainer;
      if (i < len_a)
         digits_[i] = (int)(remainer % BASE);
      else
         digits_.push_back((int)(remainer % BASE));
      remainer /= BASE;
      }

      if (remainer != 0) {
      digits_.push_back((int)remainer);
   }
   return *this;
}

bool big_int::operator ==(const big_int &b) const
{
   return compare_to(b) == 0;
}

bool big_int::operator >(const big_int &b) const
{
   return compare_to(b) > 0;
}

bool big_int::operator !=(const big_int &b) const
{
   return compare_to(b) != 0; 
}

bool big_int::operator >=(const big_int &b) const
{
   return compare_to(b) >= 0;
}

bool big_int::operator <(const big_int &b) const
{
   return compare_to(b) < 0;
}

bool big_int::operator <=(const big_int &b) const
{
   return compare_to(b) <= 0;
}

bool big_int::is_zero() const 
{
   return (digits_.size() == 1 && digits_[0] == 0);
}

big_int big_int::operator-() const
{
   big_int a = *this;
   if (is_zero())
      return a;
   a.is_negative_ = !a.is_negative_;
   return a;
}

big_int big_int::abs() const
{
   big_int a = *this;
   return (is_negative_ ? -a : a);
}

big_int& big_int::operator *=(long long b)
{
   long long remainer = 0;
   for (size_t i = 0, len = digits_.size(); i < len; i++)
   {
      remainer += b * digits_[i];
      digits_[i] = static_cast<int>(remainer % BASE);
      remainer /= BASE;
   }
   if (remainer != 0)
      digits_.push_back(static_cast<int>(remainer));
   is_negative_ = is_negative_ ^ (b < 0);
   cut_zeroes();
   return *this;
}

std::pair<big_int, big_int> big_int::divide_with_remainder(const big_int &q) const
{
	if (q == 0) {throw std::exception();}
   big_int a = abs();
   big_int b = q.abs();
   int shift = a.digits_.size() - b.digits_.size();
   if (shift < 0) 
      shift = 0;
   b <<= shift;
   fast_vector ans;
   while (shift >= 0)
   {
      int p = a.find_digit_divisor(b);
      ans.push_back(p);
      big_int tmp = b;
      tmp *= p;
      a -= tmp;
      b >>= 1;
      shift--;
   }
   ans.reverse();
   bool is_negative = is_negative_ ^ q.is_negative_;
   b = big_int(ans, is_negative);
   b.cut_zeroes();
   a.is_negative_ = is_negative_;
   if (a.is_zero())
      a.is_negative_ = false;
   if (b.is_zero())
      b.is_negative_ = false;
   return std::make_pair(b , a);
}

  
int big_int::find_digit_divisor(const big_int &q) const 
{
   if (*this < q)
      return 0;
   int l = 0, r = BASE, m;
   while (l + 1 != r)
   {
      m = (l + r) / 2;
      big_int tmp = q;
      tmp *= m;
      if (*this < tmp)
         r = m;
      else
         l = m;
   }
   return l;
}

void big_int::cut_zeroes() 
{
   int len = digits_.size();
   while (len > 1 && digits_.back() == 0)
   {
      digits_.pop_back();
      len--;
   }
}

int big_int::compare_to(const big_int &a) const
{
   if (is_negative_ && a.is_negative_)
      return -abs().compare_to(a.abs());
   if (!is_negative_ && a.is_negative_)
      return 1;
   if (is_negative_ && !a.is_negative_)
      return -1;
   if (digits_.size() != a.digits_.size())
      return (digits_.size() - a.digits_.size());
   int i = digits_.size() - 1;
   while ((i >= 0) && (digits_[i] == a.digits_[i]))
   {
      i--;
   }
   if (i == -1)
      return 0;
   return (digits_[i] - a.digits_[i]);
}

big_int& big_int::operator <<=(int shift)
{
   if (shift <= 0)
      return *this;
   fast_vector new_digits;
   new_digits.resize(shift + digits_.size());
   for (int i = 0; i < shift; i++)
   {
      new_digits[i] = 0;
   }
   for (size_t i = 0; i < digits_.size(); i++)
   {
      new_digits[i + shift] = digits_[i];
   }
   digits_ = new_digits;
   return *this;
}

big_int& big_int::operator >>=(size_t shift)
{
   if (shift >= digits_.size())
   {
      digits_.clear();
      digits_.push_back(0);
   } 
   else
   {
      digits_.erase(0, shift);
   }
   return *this;
}


std::ostream& operator <<(std::ostream& output, const big_int a)
{
   if (a.is_negative_)
      output << "-";
   output << a.digits_[a.digits_.size() - 1];
   for (size_t i = 0, len = a.digits_.size() ; i < len - 1; i++)
   {
      int tmp = a.BASE / 10;
      int x = a.digits_[len - i - 2];
      while (tmp > 0)
      {
         output << x / tmp;
         x %= tmp;
         tmp /= 10;
      }
   }
   return output;
}

std::istream& operator >>(std::istream& input, big_int& a)
{
   std::string s;

   while (!input.eof() && isspace(input.peek()))
      input.get();
   if (input.peek() == '+')
      input.get();
   else 
   if (input.peek() == '-')
      s.push_back(input.get());

   if (input.eof()) 
   {
      return input;
   }

   if (!isdigit(input.peek())) 
   {
      input.seekg(0, std::ios::end);
      input.setstate(std::ios::failbit);
      return input;
   }

   while (!input.eof() && isdigit(input.peek()))
      s.push_back(input.get());
   a = big_int(s);
   return input;
}

big_int operator +(const big_int& a, const big_int& b) 
{
   big_int q = a;
   q += b;
   return q;
}

big_int operator *(const big_int& a, const big_int& b) 
{
   big_int q = a;
   q *= b;
   return q;
}

big_int operator -(const big_int& a, const big_int& b) 
{
   big_int q = a;
   q -= b;
   return q;
}

big_int operator /(const big_int& a, const big_int& b) 
{
   big_int q = a;
   q /= b;
   return q;
}

big_int operator ^(const big_int& a, const big_int& b)
{
   if (b < 0)
      throw std::exception();
   //if (a == 0 && b == 0)
   //   throw std::exception();
   if (b == 0)
      return 1;
   big_int t = a ^ (b / 2);
   if (b % 2 == 0)
      return t * t;
   else
      return t * t * a;
}

big_int operator %(const big_int& a, const big_int& b) 
{
   big_int q = a;
   q %= b;
   return q;
}

big_int abs(const big_int& a)
{
   return a.abs();
}

